/*
 * @Author: szx
 * @Date: 2022-04-22 13:45:49
 * @LastEditTime: 2022-04-22 14:15:57
 * @Description:
 * @FilePath: \leetcode\剑指offerII\093\093.js
 */
/**
 * @param {number[]} arr
 * @return {number}
 */

var lenLongestFibSubseq = function (arr) {
    const n = arr.length;
    let set = new Set(arr),
        count = 2,
        max = 0;
    for (let i = 0; i < n - 2; i++) {
        for (let j = i + 1; j < n - 1; j++) {
            count = 2;
            let f1 = arr[i];
            let f2 = arr[j];
            let f3 = f1 + f2;
            while (set.has(f3)) {
                count++;
                if (count > max) max = count;
                f1 = f2;
                f2 = f3;
                f3 = f1 + f2;
            }
        }
    }
    return max;
};

var lenLongestFibSubseq = function (arr) {
    const n = arr.length,
        map = new Map();
    arr.forEach((v, i) => {
        map.set(v, i);
    });
    let max = 0,
        dp = new Array(n + 1).fill(0).map(() => new Array(n + 1).fill(2));
    for (let i = 0; i < arr.length - 1; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            let f2 = arr[i];
            let f3 = arr[j];
            let f1 = f3 - f2;
            if (f1 < f2 && map.has(f1)) {
                dp[i][j] = dp[map.get(f1)][i] + 1;
                max = Math.max(max, dp[i][j]);
            }
        }
    }
    return max;
};
